#include <iostream>
#include <string>
using namespace std;

typedef int DataType;
typedef struct ListNode{
	ListNode* _pNext;
	ListNode* _pPre;
	DataType _data;

	ListNode(const DataType& data = DataType())
		: _pNext(0)
		  , _pPre(0)
		  , _data(data)
	{}
}	ListNode;

class MyList{
	public:
		//无参构造
		MyList() {
			CreateHead();
		}

		//按个数构造
		MyList(size_t n, const DataType& data = DataType()) {
			CreateHead();
			for(size_t i = 0; i < n; i++) {
				PushBack(data);
			}
		}

		//按区间构造
		MyList(DataType* first, DataType* last) {
			CreateHead();
			while(first != last) {
				PushBack(*first);
				++first;
			}
		}

		//拷贝构造
		//必须深拷贝
		MyList(const MyList& L) 
		{
			CreateHead();
		//	_pHead = new ListNode;
		//	_pHead->_pNext = _pHead;
		//	_pHead->_pPre = _pHead;
			ListNode* pCur = L._pHead->_pNext;
			while(pCur != L._pHead) {
				PushBack(pCur->_data);
				pCur = pCur->_pNext;
			}
		}

		MyList& operator=(const MyList& L) { 
			if(this != &L) {
				CreateHead();
				ListNode* pCur = L._pHead;
				while(pCur != L._pHead) {
					PushBack(pCur->_data);
					pCur = pCur->_pNext;
				}
			}
			return *this;
		}

		//析构函数
		~MyList() {
			//先销毁链表中的结点，再销毁头
			//头删
			Clear();
			DestroyHead();
		}

		//有关容量的操作
		//capacity
		size_t Size()//const
		{
			size_t count = 0;
			ListNode* pCount = _pHead->_pNext;
				while(pCount != _pHead) {
					count++;
					pCount = pCount->_pNext;
				}
			return count;
		}

		//IsEmpty
		bool Empty()const
		{
			return _pHead->_pNext == _pHead;
		}

		//更新Size
		void ReSize(size_t newSize, const DataType& data = DataType())
		{
			size_t oldSize = Size();
			if(newSize <= oldSize) {
				for(size_t i = newSize; i < oldSize; ++i) {
					PopBack();
				}
			}
			else{
				for(size_t i = oldSize; i < newSize; ++i) {
					PushBack(data);
				}
			}
		}

		//有关访问操作
		DataType& Front()
		{
			return _pHead->_pNext->_data;
		}

		const DataType& Front()const
		{
			return _pHead->_pNext->_data;
		}

		DataType& Back()
		{
			return _pHead->_pPre->_data;
		}


		const DataType& Back()const
		{
			return _pHead->_pPre->_data;
		}


		//有关修改的操作
		//尾插
		void PushBack(const DataType& data)
		{
			ListNode* pNewNode = new ListNode(data);
			pNewNode->_pPre = _pHead->_pPre;
			pNewNode->_pNext = _pHead;
			_pHead->_pPre = pNewNode;
			pNewNode->_pPre->_pNext = pNewNode;
		}

		//尾删
		void PopBack()
		{
			ListNode* pDel = _pHead->_pPre;
			if(pDel != _pHead) {
				_pHead->_pPre = pDel->_pPre;
				pDel->_pPre->_pNext = _pHead;
				delete pDel;
			}
		}

		//头插
		void PushFront(const DataType& data)
		{
			ListNode* pNew = new ListNode(data);

			pNew->_pNext = _pHead->_pNext;
			pNew->_pPre = _pHead;
			_pHead->_pNext = pNew;
			pNew->_pNext->_pPre = pNew;
		}

		//头删
		void PopFront()
		{
			ListNode* pDel = _pHead->_pNext;
			if(pDel != _pHead) {
				_pHead->_pNext = pDel->_pNext;
				pDel->_pNext->_pPre = _pHead;
				delete pDel;
			}
		}

		//插入到某结点之前
		void Insert(ListNode* pPos, const DataType& data)
		{
			ListNode* pNew = new ListNode(data);
			pNew->_pPre = pPos->_pPre;
			pNew->_pNext = pPos;
			pNew->_pPre->_pNext = pNew;
			pPos->_pPre = pNew;
		}

		//任意位置删除
		void Erasae(ListNode* pPos)
		{
			if(pPos) {
				pPos->_pNext->_pPre = pPos->_pPre;
				pPos->_pPre->_pNext = pPos->_pNext;
				delete pPos;
			}
		}

		//将链表中有效结点清空
		void Clear()
		{
			ListNode* pDel = _pHead->_pNext;

			while(pDel != _pHead) {
				pDel->_pNext->_pPre = _pHead;
				_pHead->_pNext = pDel->_pNext;

				delete pDel;
				pDel = _pHead->_pNext;
			}
			_pHead->_pNext = _pHead;
			_pHead->_pPre = _pHead;
		}

	private:
		void CreateHead(){
			_pHead = new ListNode;
			_pHead->_pNext = _pHead;
			_pHead->_pPre = _pHead;
		}

		void DestroyHead() {
			delete _pHead;
			_pHead = NULL;
		}

		friend ostream& operator<<(ostream& _cout, const MyList& L)
		{
			ListNode* pCur = L._pHead->_pNext;
			while(pCur != L._pHead) {
				_cout << pCur->_data <<" ";
				pCur = pCur->_pNext;
			}
			return _cout;
		}
	private:
		ListNode* _pHead;
};

void TestMyList()
{
	MyList L1;
	MyList L2(10, 5);
	cout << L2 << endl;

	int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
	MyList L3(arr, arr + sizeof(arr)/sizeof(int));
	cout << L3 << endl;
	cout << L3.Size() << endl;
	cout << L3.Front() << endl;
	cout << L3.Back() << endl;
	L3.PushBack(1);
	L3.PushBack(2);
	L3.PushBack(3);
	L3.PushBack(4);
	L3.PushBack(5);
	L3.PushBack(6);
	cout << L3 << endl;

	L3.PopBack();
	L3.PopBack();
	cout << L3 << endl;

	L3.PushFront(0);
	cout << L3 << endl;

	L3.PopFront();
	cout << L3 << endl;

	L3.ReSize(5);
	cout << L3.Size() << endl;
	cout << L3 << endl;

	L3.ReSize(20, 9);
	cout << L3.Size() << endl;
	cout << L3 << endl;

	cout << "//////////////////////////////////////" << endl;
	MyList L4(L3);
	cout << L4 << endl;

	L3.Clear();
	cout << L3.Size() << endl;

	return;
}

int main()
{
	TestMyList();

	return 0;
}
